#include "fibonacciHeap.h"
#include "graph.h"
#include <stdlib.h>
#include <stdio.h>
#include <fstream>
#include <cassert>
#include <string>
#include <sys/time.h>
using namespace std;

#define FILE1 "results/New_Fibonaci_Iteracoes"
#define FILE2 "results/New_Fibonacci_Tempo"


vector<int> dijkstra(Graph graph, int s, int t)
{
	ofstream fileA, fileB;
	int deletemin=0, incert=0, update=0;
	struct timeval start, end;
	RootList q;
	Vertex v(0,0), u(0,0);
	AdjacencyList *n;
	AdjacencyList::iterator it;
	vector<int> dist(graph.getNumberOfNodes() + 1);
	vector<bool> visited(graph.getNumberOfNodes() + 1);
	int i;
	double iterations = 0;
	gettimeofday(&start,NULL);
	for(i = 1; i < (int)dist.size(); i++){
		if(i != s){
			dist[i] = -1;
		} else dist[i] = 0;
	}
	for(i = 1; i < (int)visited.size(); i++){
		visited[i] = false;
	}
	q.incertV(Vertex(s, 0));
	iterations = iterations +  q.numMeld;
	while(!q.isEmpty())
	{	
		v = q.deleteminV();deletemin++;
		iterations = iterations + q.numDeletemin;
		if(v.getName() == t) break;
		visited[v.getName()] = true;
		n = graph.getNeighbourhood(v.getName());
		for(it = n->begin(); it != n->end(); it++){
			u = (*it);
			if(!visited[u.getName()]){
				if(dist[u.getName()] == -1){
					dist[u.getName()] = dist[v.getName()] + u.getDist();
					q.incertV(Vertex(u.getName(), dist[u.getName()]));incert++;
					iterations = iterations + q.numMeld;
				}
				else {
					int aux = dist[u.getName()];
					dist[u.getName()] =
							(dist[v.getName()] + u.getDist()) > dist[u.getName()]
							? dist[u.getName()] : (dist[v.getName()] + u.getDist());
					q.decreasekeyV(Vertex(u.getName(), aux), dist[u.getName()]);update++;
					iterations = iterations + q.numCut;
				}
			}
		}
	}
	gettimeofday(&end,NULL);
	double executionTime = ((end.tv_sec*1000000+end.tv_usec) - (start.tv_sec*1000000+start.tv_usec))/1000;
	fileA.open(FILE1, ios_base::app);
	//fileA << s << " " << t << " " << dist[t] << " "  << deletemin << " " << incert << " "  << update << " " << executionTime << endl;
	fileA << graph.getNumberOfNodes() << " " << iterations << endl; 
	fileA.close();
	fileB.open(FILE2, ios_base::app);
	fileB << graph.getNumberOfNodes() << " " << executionTime << endl;
        fileB.close();
	return dist;
}


int main(int argc, char *argv[])
{
	//assert(argc == 3);
	Graph graph;
	ofstream file1, file2;

	srand48(time(0));

	file1.open(FILE1);
	//file1 << "Source Target Distance Deletemin incert update Time(miliseconds)" << endl;
	file1 << "# numNodes iteracoes" << endl;
	//file1 << "NumNodes delete+incert+update" << endl;
	file1.close();

	file2.open(FILE2);
        file2 << "# numNodes Time(miliseconds)" << endl;
        file2.close();

	
	graph.loadGraph();
	for(int i = 0; i < 150; i++) {
		dijkstra(graph, lrand48()%(graph.getNumberOfNodes()+1), lrand48()%(graph.getNumberOfNodes()+1));
	}
	/*char buffer[256];	
	for(int i = 2; i<=100; i++){
		sprintf(buffer, "./testCaseGenerator %d %d case%d.txt", i, i, i);
		system(buffer);
		sprintf(buffer, "case%d.txt", i);
		graph.loadGraphFromFile(buffer);
        	dijkstra(graph, 1, 2);	
		sprintf(buffer, "rm case%d.txt", i);
		system(buffer);
	}*/	

	return 0;
}

